function List() {
    this.data = [{data:null, next:null}];
    this.empty_ptr = [];
    this.supply_nodes_count = 16;
    this.tail = 0;
    this.size = 0;

    this.extend_space_if_full = function() {
        if(this.empty_ptr.length == 0) {
            for(var i = 0; i < this.supply_nodes_count; i++) {
                this.data.push({data:null, next:null});
                this.empty_ptr.push(this.data.length - 1);
            }
        }
    }

    this.push_back = function(data) {
        this.extend_space_if_full();
        var new_ptr = this.empty_ptr.pop();
        this.data[new_ptr].data = data;
        this.data[new_ptr].next = null;
        this.data[this.tail].next = new_ptr;
        this.tail = new_ptr;
        this.size += 1;
    }

    this.pop_front = function() {
        var old_head_ptr = this.data[0].next;
        var old_head_data = this.data[old_head_ptr].data;
        this.data[0].next = this.data[old_head_ptr].next;
        this.empty_ptr.push(old_head_ptr);
        this.size -= 1;
        return old_head_data;
    }

    // offset越界时，插入到链表尾部
    // ptr为空时，直接push_back
    this.insert = function(data, ptr, offset) {
        if(ptr == null) {
            this.push_back(data);
            return;
        }
        for(var i = 0; i < offset; i++) {
            if(this.data[ptr].next == null) {
                break;
            }
            ptr = this.data[ptr].next;
        }
        this.extend_space_if_full();
        var new_ptr = this.empty_ptr.pop();
        this.data[new_ptr].data = data;
        this.data[new_ptr].next = this.data[ptr].next;
        this.data[ptr].next = new_ptr;
        if(ptr == this.tail) {
            this.tail = new_ptr;
        }
        this.size += 1;
    }

    this.get_head_ptr = function() {
        return this.data[0].next;
    }
}

